# Definition for a binary tree node.
from collections import deque
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        d = deque([root, root])
        while d:
            node1, node2 = d.pop(), d.pop()
            if not node1 and not node2: continue
            if not (node1 and node2): return False
            if node1.val != node2.val: return False
            # print(node1.val, node2.val)
            d.append(node1.left)
            d.append(node2.right)
            d.append(node1.right)
            d.append(node2.left)
        return True
if __name__ == '__main__':
    root = TreeNode(1)
    left1, right1 = TreeNode(2), TreeNode(2)
    left21, right21, left22, right22 = TreeNode(3), TreeNode(4), TreeNode(4), TreeNode(3)
    root.left, root.right = left1, right1
    left1.left, left1.right = left21, right21
    right1.left, right1.right = left22, right22
    s = Solution()
    result = s.isSymmetric(root)
    print(result)
